package datastructure.book.tujiesuanfa.tree._1_all;

import datastructure.book.tujiesuanfa.tree.bean.Node;
import datastructure.book.tujiesuanfa.tree.bean.TreeNode;
import org.junit.jupiter.api.Test;

import java.util.LinkedList;
import java.util.List;

public class Solution1 {
    /**
     * 从上往下，从左到右遍历树
     */
    public int[] decorateRecord(TreeNode root) {
        int[] result = new int[0];
        if (root == null) {
            return result;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.removeFirst();
            int[] temp = new int[result.length+1];
            System.arraycopy(result,0,temp,0,result.length);
            temp[temp.length-1] = node.val;
            result = temp;
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return result;
    }
    /**
     * 从上往下，从左到右遍历树，每一层的结果放在一个list里
     */
    public List<List<Integer>> decorateRecord2(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<>();
        if (root == null) {
            return result;
        }
        LinkedList<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.add(root);
        int cnt = 1;
        while (!treeNodes.isEmpty()) {
            LinkedList<Integer> integers = new LinkedList<>();
            int tempCnt = 0;
            for (int i = 0; i < cnt; i++) {
                TreeNode node = treeNodes.removeFirst();
                integers.add(node.val);
                if (node.left != null) {
                    treeNodes.add(node.left);
                    tempCnt++;
                }
                if (node.right != null) {
                    treeNodes.add(node.right);
                    tempCnt++;
                }
            }
            result.add(integers);
            cnt = tempCnt;
        }
        return result;
    }
    /**
     * 第一层从左往右遍历，其余每层遍历顺序与上一层相反，每一层的结果放在一个list里
     * 第一层：从左往右、第二层：从右往左、第三层：从左往右
     */
    public List<List<Integer>> decorateRecord3(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<>();
        if (root == null) {
            return result;
        }
        LinkedList<TreeNode> treeNodes = new LinkedList<>();
        boolean flag = true;
        treeNodes.add(root);
        while (!treeNodes.isEmpty()) {
            LinkedList<Integer> integers = new LinkedList<>();
            int cnt = treeNodes.size();
            LinkedList<TreeNode> tempNode = new LinkedList<>();
            for (int i = 0; i < cnt; i++) {
                TreeNode node;
                if (flag) {
                    node = treeNodes.removeFirst();
                    if (node.left != null) {
                        tempNode.add(node.left);
                    }
                    if (node.right != null) {
                        tempNode.add(node.right);
                    }
                } else {
                    node = treeNodes.removeLast();
                    if (node.right != null) {
                        tempNode.addFirst(node.right);
                    }
                    if (node.left != null) {
                        tempNode.addFirst(node.left);
                    }
                }
                integers.add(node.val);
            }
            result.add(integers);
            flag = !flag;
            treeNodes = tempNode;
        }
        return result;
    }

    /**
     * 两棵二叉树 tree1 和 tree2，
     * 判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值
     * tree2为空返回false
     * tree1:
     *        [3]
     *    [6]     [7]
     * [1]  [8] []  []
     * tree2:
     *         [6]
     *       [1]  []
     * tree2 与 tree1 的一个子树拥有相同的结构和节点值。即 6 - > 1。
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null && B == null) {
            return false;
        }
        if (A == null || B == null) {
            return false;
        }
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(A);
        while (!list.isEmpty()) {
            TreeNode node = list.removeLast();
            if (haveSubStructure(node, B)) {
                return true;
            }
            if (node.right != null) {
                list.add(node.right);
            }
            if (node.left != null) {
                list.add(node.left);
            }
        }
        return false;
    }

    private boolean haveSubStructure(TreeNode aNode, TreeNode bNode){
        if (aNode.val != bNode.val) {
            return false;
        }
        LinkedList<TreeNode> listA = new LinkedList<>();
        LinkedList<TreeNode> listB = new LinkedList<>();
        do {
            if (bNode.right != null) {
                if (aNode.right == null) {
                    return false;
                }
                if (aNode.right.val != bNode.right.val) {
                    return false;
                }
                listA.add(aNode.right);
                listB.add(bNode.right);
            }
            if (bNode.left != null) {
                if (aNode.left == null) {
                    return false;
                }
                if (aNode.left.val != bNode.left.val) {
                    return false;
                }
                listA.add(aNode.left);
                listB.add(bNode.left);
            }
            aNode = listA.pollLast();
            bNode = listB.pollLast();
        } while (aNode != null && bNode != null);
        return true;
    }

    /**
     * 翻转二叉树，翻转每个节点的左右节点
     * 翻转前
     *                 4
     *             2       3
     *          4   5   6   7
     *        8   9
     * 翻转后
     *                 4
     *             3       2
     *          7   6   5   4
     *                    9   8
     */
    public TreeNode flipTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        flipTree1(root);
        return root;
    }

    private void flipTree1(TreeNode root) {
        if (root == null) {
            return;
        }
        flipTree1(root.left);
        flipTree1(root.right);
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = temp;
    }

    /**
     * 判断一棵二叉树是否轴对称
     * 例：对称二叉树
     *           1
     *     2          2
     *        3    3
     */
    public boolean checkSymmetricTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        return checkSymmetricTree0(root.left, root.right);
    }

    private boolean checkSymmetricTree0(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return checkSymmetricTree0(left.left,right.right)
                && checkSymmetricTree0(left.right,right.left);
    }

    /**
     * 将二叉搜索树转化为排序的双向链表
     * 将左右孩子指针作为双向循环链表的前驱和后继指针，
     * 第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点
     * 返回链表中最小元素的指针
     * Node.left.val < Node.val < Node.right.val
     *              4
     *      2               7
     *   1     3        6       8
     *               5
     *   [8]<=>1<=>2<=>3<=>4<=>5<=>6<=>7<=>8<=>[1]
     */
    public Node treeToDoublyList(Node root) {
        Node[] nodes = new Node[]{root,null,null};
        orderTree(nodes);
        if (nodes[1] != null && nodes[2] != null) {
            nodes[1].left = nodes[2];
            nodes[2].right = nodes[1];
        }
        return nodes[1];
    }

    private void orderTree(Node[] nodes) {
        Node root = nodes[0];
        if (root == null) {
            return;
        }
        nodes[0] = root.left;
        orderTree(nodes);
        if (nodes[1] == null) {
            nodes[1] = root;
        } else {
            nodes[2].right = root;
            root.left = nodes[2];
        }
        nodes[2] = root;
        nodes[0] = root.right;
        orderTree(nodes);
    }

    /**
     * 寻找二叉搜索树中的第N大的数
     * 例：
     *              10
     *        5            15
     *   2         7             20
     * 1        6     8
     * 第4大的数为：8
     * [1,2,5,6,7,8,10,15,20]
     */
    public int findTargetNode(TreeNode root, int cnt) {
        int[] result = {0, cnt, 0};
        findTargetNode0(root,result);
        return result[2];
    }

    private void findTargetNode0(TreeNode root, int[] ints) {
        if (root == null) {
            return;
        }
        findTargetNode0(root.right,ints);
        if (ints[0] == ints[1]) {
            return;
        }
        ints[0]++;
        if (ints[0] == ints[1]) {
            ints[2] = root.val;
            return;
        }
        findTargetNode0(root.left,ints);
    }

    /**
     * 计算二叉树的深度
     * 例：深度为4的二叉树
     *              10
     *        5            15
     *   2         7             20
     * 1        6     8
     */
    public int calculateDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        int cnt = 0;
        int nodeCnt = 1;
        while (!list.isEmpty()) {
            int tempNodeCnt = 0;
            for (int i = 0; i < nodeCnt; i++) {
                TreeNode node = list.removeFirst();
                if (node.left != null) {
                    list.add(node.left);
                    tempNodeCnt++;
                }
                if (node.right != null) {
                    list.add(node.right);
                    tempNodeCnt++;
                }
            }
            nodeCnt = tempNodeCnt;
            cnt++;
        }
        return cnt;
    }

    /**
     * 判断是否为平衡二叉树
     * 二叉树中任意节点的左右子树的深度相差不超过1那么它就是一棵平衡二叉树
     * 例：平衡二叉树
     *              10
     *        5            15
     *   2         7             20
     * 1        6     8
     * 非平衡二叉树
     *              10
     *        5            15
     *   2         7             20
     * 1        6     8
     *       3
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean[] result = {true};
        isBalanced0(root,result);
        return result[0];
    }

    private int isBalanced0(TreeNode root, boolean[] result) {
        if (root == null) {
            return 0;
        }
        int leftDepth = isBalanced0(root.left,result);
        if (!result[0]) {
            return 0;
        }
        int rightDepth = isBalanced0(root.right,result);
        if (!result[0]) {
            return 0;
        }
        if (Math.abs(leftDepth - rightDepth) > 1) {
            result[0] = false;
            return 0;
        }
        return Math.max(leftDepth,rightDepth)+1;
    }

    /**
     * 寻找二叉搜索树的最近公共祖先
     * 例：4   6 最近公共祖先为 4
     *           7
     *       3         8
     *   2    4
     * 1    5    6
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        int val = root.val;
        int val1 = p.val;
        int val2 = q.val;
        if (val1 < val && val < val2) {
            return root;
        }
        if (val1 > val && val > val2) {
            return root;
        }
        if (val1 == val || val2 == val) {
            return root;
        }
        if (val1 < val) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return lowestCommonAncestor(root.right, p, q);
        }
    }

    @Test
    public void testLowestCommonAncestor2(){
        TreeNode treeNode3 = new TreeNode(3, null, null);
        TreeNode treeNode8 = new TreeNode(8, null, null);
        TreeNode treeNode_2 = new TreeNode(-2, treeNode8, null);
        TreeNode treeNode4 = new TreeNode(4, null, null);
        TreeNode treeNode0 = new TreeNode(0, treeNode_2, treeNode4);
        TreeNode treeNode_1 = new TreeNode(-1, treeNode0, treeNode3);
        System.out.println(lowestCommonAncestor2(treeNode_1, treeNode3, treeNode8));
    }

    /**
     * 寻找二叉树的最近公共祖先
     * 例：3   8 最近公共祖先为 -1
     *           -1
     *       0         3
     *   -2    4
     * 8
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root.val == p.val || root.val == q.val) {
            return root;
        }
        int cnt = findNode(root.left,p,q);
        if (cnt == 0) {
            return lowestCommonAncestor2(root.right,p,q);
        }
        if (cnt == 1) {
            return root;
        } else {
            return lowestCommonAncestor2(root.left, p, q);
        }
    }

    private int findNode(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return 0;
        }
        int cnt = 0;
        if (root.val == p.val || root.val == q.val) {
            cnt = 1;
        }
        return findNode(root.left,p,q)+findNode(root.right,p,q)+cnt;
    }
}
